package codingforgreat.class16;

import java.util.Arrays;

//lc 330
public class Class03_MinPatches {
    public static int minPatches(int[] nums, int n) {
        int path = 0;
        long range = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            while(range < nums[i] - 1){
                range += range + 1;
                path++;
                if (range >= n) {
                    return path;
                }
            }
            range += nums[i];
            if(range >= n){
                return path;
            }
        }
        while( range < n){
            range += range + 1;
            path++;
        }
        return path;
    }
}
